Sudoku al estilo de P. Norvig ============================= Esta solución al Sudoku es una mínima re-escritura de la `solución dada por Peter Norvig en su página `__. Los cambios tan solo pretenden eliminar las decisiones sutiles, que no son propias de un aprendiz. Tal es el caso de la codificación de filas, columnas y valores como cadenas para evitar el uso de ``deepcopy``. Nosotros codificaremos las casillas con sus coordenadas cartesianas, como una simple tupla y los valores como conjuntos de números. En primer lugar vamos a definir las estructuras que emplea Peter Norvig. Piénsalas tú mismo en casa, no las leas sin más. Escribe tú mismo una función que las calcule y emplea tantas funciones como necesites. - Cada casilla es una tupla ``(x,y)`` con las coordenadas cartesianas. - ``squares`` es una lista de todas las casillas del Sudoku. - ``unitlist`` es una lista de todas las unidades. Una unidad es a su vez una lista de 9 casillas que no pueden contener nada más que una cifra de cada. Es decir, ``unitlist`` contiene listas de 9 casillas que corresponden a las filas, columnas y bloques. - ``units`` es un diccionario que asocia con cada casilla del Sudoku todas las unidades a las que pertenece dicha casilla. - ``peers`` (colegas) es un diccionario que asocia a cada casilla del Sudoku la lista de casillas que están en su misma fila, columna o bloque, sin incluirla. .. code:: python squares = [ (x,y) for y in range(9) for x in range(9) ] blocks = [ (0,1,2), (3,4,5), (6,7,8) ] unitlist = [ [ (x,y) for x in range(9) ] for y in range(9) ] + \ [ [ (x,y) for y in range(9) ] for x in range(9) ] + \ [ [ (x,y) for x in bx for y in by ] for bx in blocks for by in blocks ] units = { s: [u for u in unitlist if s in u] for s in squares } peers = { s: set(sum(units[s],[])) - { s } for s in squares } Vamos ahora a definir funciones para convertir una cadena de texto a un Sudoku. El Sudoku lo modelaremos como un diccionario que hace corresponder a cada casilla con el conjunto de números que puede contener dicha casilla. Es prácticamente una trasliteración del código de Peter Norvig, por lo que no merece la pena comentarlo con mucho más detalle. La función ignora cualquier carácter que no sea una cifra o un punto. El punto o el 0 representan casillas sin rellenar. Inicialmente el Sudoku está vacío. Es decir, cada casilla puede contener cualquier cifra. Lo modelamos con la variable ``values`` que no es más que un diccionario que hace corresponder cada casilla al conjunto de valores permitidos en esa casilla. Usamos conjuntos (``set``) porque se esta forma garantizamos que no hay repetidos y además podemos eliminar elementos empleando el operador de resta. Cada vez que conocemos una casilla con un dígito fijo (de 1 a 9) podemos asignar ese valor a la casilla eliminado el resto. Esta asignación hace que podamos simplificar otras casillas (propagación de restricciones). .. code:: python digits = range(1,10) def parse_grid(grid): values = { s:set(digits) for s in squares } for s,d in grid_values(grid).items(): if d in digits: asignar(values, s, { d }) return values def grid_values(grid): values = [ gvalue(c) for c in grid if c in '.1234567890' ] assert len(values) == 81 return dict(zip(squares, values)) def gvalue(c): return int(c) if c in '123456789' else 0 El punto clave de la solución del Sudoku es la propagación de restricciones. Básicamente consiste en la combinación de dos funciones que cooperan entre sí, una para asignar valores a una casilla y otra para eliminar valores de una casilla. Cuando se asigna un valor en una casilla, debe eliminarse de todos sus ``peers``. Al eliminar valores de una casilla puede que queden nuevas casillas con un único valor, que daría lugar a nuevas eliminaciones. También puede que solo quede una casilla posible donde poner alguna de las cifras, por lo que daría lugar a la asignación de esta cifra. .. code:: python def asignar(values, s, d): other_values = values[s] - d eliminar(values, s, other_values) def eliminar(values, s, d): if not d.intersection(values[s]): return values[s] -= d if len(values[s]) == 0: raise ValueError('Casilla {0} sin valores posibles'.format(s)) ## (1) Si una casilla se queda con un solo valor, eliminarlo de sus colegas. if len(values[s]) == 1: for s2 in peers[s]: eliminar(values, s2, values[s]) ## (2) Si solo hay una casilla de una unidad para el digito d asignarlo a esa casilla. for u in units[s]: dplaces = [s for s in u if d.intersection(values[s])] if len(dplaces) == 0: raise ValueError('No hay casilla para valor {0} en unidad {1}'.format(d,u)) elif len(dplaces) == 1: asignar(values, dplaces[0], d) Va siendo hora de escribir una función para mostrar el Sudoku. Dibujaremos líneas para separar los bloques. Lo más destacable es el cálculo del ancho de cada casilla, que depende de cuántas cifras posibles tienen todas las casillas del Sudoku. .. code:: python def display(values): width = 1+max(len(values[s]) for s in squares) line = '+'.join(['-'*(width*3)]*3) for r in range(9): print(''.join(''.join([str(i) for i in values[(c,r)]]).center(width)+('|' if c in (2,5) else '') for c in range(9))) if r in (2,5): print(line) print() Solo con esto ya se resuelven prácticamente todos los Sudokus fáciles. .. code:: python grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300' display(parse_grid(grid1)) .. parsed-literal:: 4 8 3 |9 2 1 |6 5 7 9 6 7 |3 4 5 |8 2 1 2 5 1 |8 7 6 |4 9 3 ------+------+------ 5 4 8 |1 3 2 |9 7 6 7 2 9 |5 6 4 |1 3 8 1 3 6 |7 9 8 |2 4 5 ------+------+------ 3 7 2 |6 8 9 |5 1 4 8 1 4 |2 5 3 |7 6 9 6 9 5 |4 1 7 |3 8 2 En algunos casos la propagación de restricciones sigue dejando un Sudoku muy poco especificado. .. code:: python grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' display(parse_grid(grid2)) .. parsed-literal:: 4 1679 12679 | 139 2369 1269 | 8 1239 5 26789 3 1256789 | 14589 24569 1245689 | 12679 1249 124679 2689 15689 125689 | 7 234569 1245689 | 12369 12349 123469 ------------------------+------------------------+------------------------ 3789 2 135789 | 3459 34579 4579 | 13579 6 13789 3679 15679 135679 | 359 8 25679 | 4 12359 12379 36789 4 356789 | 359 1 25679 | 23579 23589 23789 ------------------------+------------------------+------------------------ 289 89 289 | 6 459 3 | 1259 7 12489 5 6789 36789 | 2 479 14789 | 1369 13489 134689 1 6789 4 | 589 579 5789 | 23569 23589 23689 Aparentemente el número de posibilidades es aún muy elevado: .. code:: python def nposibles(values): n = 1 for s,v in values.items(): n *= len(v) return n print(nposibles(parse_grid(grid2))) .. parsed-literal:: 181432630923264000000000000000000000000000 Sin embargo si dirigimos adecuadamente la búsqueda el resultado puede ser muy rápido. Tomar una decisión sobre el valor de una casilla que tiene nueve posibilidades nos da un 11% de probabilidad de acierto. Sin embargo elegir una de las opciones de una casilla que solo tenga dos posibilidades nos da un 50% de probabilidad de acierto, y al propagar las restricciones se reduce la cardinalidad de las demás casillas, aumentando correspondientemente la probabilidad de acierto. .. code:: python def solve(grid): return search(parse_grid(grid)) from copy import deepcopy def search(values): if all(len(values[s]) == 1 for s in squares): return values ## Elige la casilla sin fijar con menos posibilidades n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1) return intentar_todos(values, s) def intentar_todos(values, s): for d in values[s]: try: tentativa = deepcopy(values) asignar(tentativa, s, { d }) return search(tentativa) except ValueError: pass raise ValueError('No hay solucion') .. code:: python display(solve(grid2)) .. parsed-literal:: 4 1 7 |3 6 9 |8 2 5 6 3 2 |1 5 8 |9 4 7 9 5 8 |7 2 4 |3 1 6 ------+------+------ 8 2 5 |4 3 7 |1 6 9 7 9 1 |5 8 6 |4 3 2 3 4 6 |9 1 2 |7 5 8 ------+------+------ 2 8 9 |6 4 3 |5 7 1 5 7 3 |2 9 1 |6 8 4 1 6 4 |8 7 5 |2 9 3 .. code:: python hard1 = ''' . . . |. . 6 |. . . . 5 9 |. . . |. . 8 2 . . |. . 8 |. . . ------+------+------ . 4 5 |. . . |. . . . . 3 |. . . |. . . . . 6 |. . 3 |. 5 4 ------+------+------ . . . |3 2 5 |. . 6 . . . |. . . |. . . . . . |. . . |. . .''' display(solve(hard1)) .. parsed-literal:: 3 8 4 |5 1 6 |9 2 7 6 5 9 |4 7 2 |1 3 8 2 7 1 |9 3 8 |6 4 5 ------+------+------ 8 4 5 |2 6 9 |7 1 3 1 2 3 |7 5 4 |8 6 9 7 9 6 |1 8 3 |2 5 4 ------+------+------ 9 1 8 |3 2 5 |4 7 6 4 3 2 |6 9 7 |5 8 1 5 6 7 |8 4 1 |3 9 2 .. code:: python hard2 = ''' . . 5 |3 . . |. . . 8 . . |. . . |. 2 . . 7 . |. 1 . |5 . . ------+------+------ 4 . . |. . 5 |3 . . . 1 . |. 7 . |. . 6 . . 3 |2 . . |. 8 . ------+------+------ . 6 . |5 . . |. . 9 . . 4 |. . . |. 3 . . . . |. . 9 |7 . . ''' display(solve(hard2)) .. parsed-literal:: 1 4 5 |3 2 7 |6 9 8 8 3 9 |6 5 4 |1 2 7 6 7 2 |9 1 8 |5 4 3 ------+------+------ 4 9 6 |1 8 5 |3 7 2 2 1 8 |4 7 3 |9 5 6 7 5 3 |2 9 6 |4 8 1 ------+------+------ 3 6 7 |5 4 2 |8 1 9 9 8 4 |7 6 1 |2 3 5 5 2 1 |8 3 9 |7 6 4